/*********************************************************
          File Name: string_find.cc
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: Mon 27 Aug 2018 08:50:46 PM CST
**********************************************************/

#include <iostream>
#include <string>
#include <boost/timer.hpp>

size_t my_find(const std::string& src, const std::string& dst)
{
  static const size_t npos = (size_t)-1;
  size_t sl = src.size();
  size_t dl = dst.size();
  size_t j = 0;
  size_t i = 0;
  for(; i < sl; ++i)
  {
    if(j == dl)
    {
      return i - dl;
    }
    if(src[i] == dst[j])
    {
      if(i > 0 && j > 0 && src[i-1] != dst[j-1])
      {
        return npos;
      }
      ++j;
    }
  }
  return j == dl ? i - j : npos;
}

int main(int argc, char* argv[])
{
  // when partten's length is less than half of string's length
  // my_find will be faster then string.find
  if(argc != 4)
  {
    fprintf(stderr, "%s src dst n\n", argv[0]);
    return 1;
  }
  std::string src{argv[1]};
  std::string dst{argv[2]};
  size_t n = std::stoull(argv[3]);
  size_t m_c = 0;
  size_t s_c = 0;
  std::cerr << std::fixed;
  boost::timer t;
  t.restart();
  for(size_t i = 0; i < n; ++i)
  {
    s_c += src.find(dst);
  }
  std::cerr << "string.find: " << t.elapsed() << "s s_c: " << s_c << '\n';
  t.restart();
  for(size_t i = 0; i < n; ++i)
  {
    m_c += my_find(src, dst);
  }
  std::cerr << "my_find:     " << t.elapsed() << "s m_c: " << m_c << '\n';
}
